package org.apache.commons.graph.algorithms.coloring

import org.apache.commons.graph.CommonsGraph.coloring
import org.apache.commons.graph.CommonsGraph.newUndirectedMutableGraph
import org.apache.commons.graph.algorithms.coloring.exception.NotEnoughColorsException
import org.apache.commons.graph.builder.AbstractGraphConnection
import org.apache.commons.graph.model.BaseLabeledEdge
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.UndirectedMutableGraph
import org.apache.commons.graph.utils.GraphUtils
import org.junit.Assert
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 *
 */
class GraphColoringTestCase : org.apache.commons.graph.algorithms.coloring.AbstractColoringTest() {
    private val colors = createColorsList(11)

    /**
     * see [wiki](http://en.wikipedia.org/wiki/Crown_graph) for more details
     */
    @Test
    fun testCrawnGraph() {
        val g =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
        GraphUtils.buildCrownGraph(6, g)

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> = coloring(g).withColors(colors).applyingGreedyAlgorithm()
        checkColoring(g, coloredVertices)
    }

    @Test
    @Throws(Exception::class)
    fun testCromaticNumber() {
        val g: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    val one = addVertex(BaseLabeledVertex("1"))
                    val two = addVertex(BaseLabeledVertex("2"))
                    val three = addVertex(BaseLabeledVertex("3"))

                    addEdge(BaseLabeledEdge("1 -> 2")).from(one).to(two)
                    addEdge(BaseLabeledEdge("2 -> 3")).from(two).to(three)
                    addEdge(BaseLabeledEdge("3 -> 1")).from(three).to(one)
                }
            })

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g).withColors(colors).applyingGreedyAlgorithm()
        checkColoring(g, coloredVertices)
    }

    @Test
    fun testCromaticNumberBiparted() {
        val g1 =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
        GraphUtils.buildBipartedGraph(100, g1)

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(colors).applyingGreedyAlgorithm()

        checkColoring(g1, coloredVertices)
    }

    @Test
    fun testCromaticNumberComplete() {
        val g1 =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
        GraphUtils.buildCompleteGraph(100, g1)

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(createColorsList(100)).applyingGreedyAlgorithm()
        checkColoring(g1, coloredVertices)
    }

    @Test
    fun testCromaticNumberSparseGraph() {
        val g1 =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
        for (i in 0..99) {
            g1.addVertex(BaseLabeledVertex(i.toString()))
        }

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(colors).applyingGreedyAlgorithm()

        Assert.assertEquals(1, coloredVertices.requiredColors.toLong())
        checkColoring(g1, coloredVertices)
    }

    @Test
    fun testEmptyGraph() {
        val g = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()

        val coloredVertices: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g).withColors(createColorsList(1)).applyingGreedyAlgorithm()
        Assert.assertNotNull(coloredVertices)
        Assert.assertEquals(0, coloredVertices.requiredColors.toLong())
    }

    @Test(expected = NotEnoughColorsException::class)
    fun testNotEnoughtColorGreedyGraph() {
        val two = BaseLabeledVertex("2")

        val g: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> =
            newUndirectedMutableGraph(object : AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>() {
                override fun connect() {
                    val one = addVertex(BaseLabeledVertex("1"))
                    addVertex(two)
                    val three = addVertex(BaseLabeledVertex("3"))

                    addEdge(BaseLabeledEdge("1 -> 2")).from(one).to(two)
                    addEdge(BaseLabeledEdge("2 -> 3")).from(two).to(three)
                    addEdge(BaseLabeledEdge("3 -> 1")).from(three).to(one)
                }
            })
        coloring(g).withColors(createColorsList(1)).applyingGreedyAlgorithm()
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullColorGraph() {
//        val g =
//            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
//
//        coloring(g).withColors(null).applyingBackTrackingAlgorithm()
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        coloring(null as UndirectedGraph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?).withColors(null)
//            .applyingGreedyAlgorithm()
//    }

    @Test
    @Throws(Exception::class)
    fun testSudoku() {
        val g1 = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>()
        GraphUtils.buildSudokuGraph(g1)

        //Optimal solution is to use 9 colors, not all algorithms can find solution with minimal colors.
        //greedy algorithm needs 13 colors to fetch solution ATM.
        val col = createColorsList(9)

        val sudoku: ColoredVertices<BaseLabeledVertex, Int> =
            coloring(g1).withColors(col).applyingBackTrackingAlgorithm()
        checkColoring(g1, sudoku)
    }
}
